package org.example.recursion;

/**
 * @author carol
 */
public class BubbleSort {
    public static void sort(int[] a){
        //bubble(a,a.length-1);
        bubble1(a,a.length-1);
    }

    private static void bubble(int[] a,int n){
        // 检查数组是否已经有序，退出递归
        if(n==0){
            return;
        }
        //n为未排序区域右边界
        for (int i = 0;i<n;i++){
            if (a[i] > a[i+1]){
                //交换
                int temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
            }
        }
        bubble(a,--n);
    }

    private static void bubble1(int[] a,int n){
        /*
        定义 x代表右边界，当发生两数交换时将 i 赋值给 x ，最后一次赋给x后，x右边的都为有序，将x作为右边界传给下一次递归
         */
        if(n==0){
            return;
        }
        //右边界
        int x = 0;
        //n为未排序区域右边界
        for (int i = 0;i<n;i++){
            if (a[i] > a[i+1]){
                //交换
                int temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
                x = i;
            }
        }
        bubble(a,x);
    }

    public static void main(String[] args) {
        int[] a = {1,12,32,54,15,16,3};
        sort(a);
        for (int i : a) {
            System.out.println(i);
        }
    }

}
